package week02

// 94. 二叉树的中序遍历
// https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

func inorderTraversal(root *TreeNode) []int {
	return inorderTraversal2(root, []int{})
}

func inorderTraversal2(root *TreeNode, ans []int) []int {
	if root == nil {
		return ans
	}
	ans = inorderTraversal2(root.Left, ans)
	ans = append(ans, root.Val)
	ans = inorderTraversal2(root.Right, ans)
	return ans
}

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}